package leetcode_ago.LinearList;

/**
 * 分割链表
 * 给你一个链表的头节点 head 和一个特定值x，请你对链表进行分隔，使得所有小于x的节点都出现在大于或等于x的节点之前。
 * 你不需要保留每个分区中各节点的初始相对位置。
 */

/**
 * 思路：
 * 1.边遍历原链表边将原链表中的节点依照与x的大小关系放在small与big中
 * 2.small与big合并，big尾部元素注意置空
 */
public class NumJZ0204_SplitList {
    public ListNode partition(ListNode head, int x) {
        //创建small和big两个小链表的头节点【虚拟头节点】
        ListNode smallHead=new ListNode(-1);
        ListNode bigHead=new ListNode(-1);
        //遍历原链表,没有说保留原链表，可以直接用head操作
        //再用两个引用分别指向子链表的尾部
        ListNode smallTail=smallHead;
        ListNode bidTail=bigHead;
        while (head!=null){
            if(head.val<x){
                smallTail.next=head;
                smallTail=head;
            }else{
                bidTail.next=head;
                bidTail=head;
            }
            head=head.next;
        }
        smallTail.next=bigHead.next;
        bidTail.next=null;
        return smallHead.next;
    }
}
